package bintree.nowcode;

//JZ36 二叉搜索树与双向链表

public class JZ36 {
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree==null){
            return null;
        }
        TreeNode leftHead = Convert(pRootOfTree.left);
        TreeNode leftTail = leftHead;
        while (leftTail!=null && leftTail.right!=null){
            leftTail=leftTail.right;
        }
        if(leftTail!=null){
            pRootOfTree.left=leftTail;
            leftTail.right=pRootOfTree;
        }
        TreeNode rightHead = Convert(pRootOfTree.right);
        if(rightHead!=null){
            pRootOfTree.right = rightHead;
            rightHead.left = pRootOfTree;
        }

        return leftHead == null ? pRootOfTree : leftHead;
    }
}
